package com.leetcode;

/**
 * 1823. 找出游戏的获胜者
 *
 * 2022-05-04 每日一题
 *
 * @author fy
 * @date 2022-05-04 16:21
 */
public class Solution1823 {

    public int findTheWinner(int n, int k) {
        int[] players = new int[n];
        for (int i = 0; i < n; i++) {
            players[i] = i + 1;
        }
        return playGame(players, 0, k);
    }

    private int playGame(int[] players, int index, int k) {
        int n = players.length;
        if (n == 1) {
            return players[0];
        }
        int left = (index - 1 + k) % n;
        int[] pl = new int[n - 1];
        int j = 0;
        int idx = 0;
        for (int i = 0; i < n; i++) {
            if (i != left) {
                pl[j++] = players[i];
            } else {
                idx = (i % (n - 1));
            }
        }
        if (idx > n - 1) {
            idx = 0;
        }
        return playGame(pl, idx, k);
    }


    public static void main(String[] args) {
        int n = 5;
        int k = 2;
        int res = new Solution1823().findTheWinner(n, k);
        System.out.println(res);
    }

}
